1
Приближение неравенств: от функций индикаторов к гладким барьерам
MATH008Lesson 11
00:00
Представьте, что вы управляете алгоритмом высокочастотной торговли. Ваш портфель имеет строгий лимит риска. «Жесткое» ограничение действует как аварийный тормоз — оно мгновенно останавливает все процессы при достижении лимита, что может привести к сбоям в логике системы. В выпуклой оптимизации мы предпочитаем «мягкую» систему предупреждений. Мы заменяем резкий, двоичный «обрыв» функции индикатора на плавный, логарифмический «барьер», который всё больше штрафует целевую функцию по мере приближения к границе. Это позволяет оптимизатору «почувствовать» приближающееся ограничение и плавно скорректировать свою траекторию, не выходя за допустимые границы никогда.

Проблема недифференцируемости

Стандартная задача оптимизации с ограничениями определяется следующим образом:

$$\text{минимизировать } f_0(x) \\ \text{при условии } f_i(x) \leq 0, \quad i = 1, \ldots, m \\ Ax = b$$

Теоретически мы могли бы переписать это с использованием функции индикатора $I_-(u)$ для поглощения ограничений в целевой функции. Однако $I_-(u)$ — это чудовище для математического анализа:

$$I_-(u) = \begin{cases} 0 & u \leq 0 \\ \infty & u > 0 \end{cases}$$

Поскольку она разрывна и имеет бесконечный градиент на границе, мы не можем вычислить гессиан, необходимый для Метод Ньютона. Нам нужна дифференцируемая аппроксимация.

Логарифмическое сглаживание

Аппроксимация

Мы аппроксимируем $I_-(u)$ с помощью функции:

$$\hat{I}_-(u) = -(1/t) \log(-u), \quad \text{обл. определения } \hat{I}_- = -\mathbf{R}_{++}$$

Здесь $t > 0$ — параметр, определяющий точность нашей аппроксимации. Чем больше $t$, тем ближе барьер приближается к истинной функции индикатора.

Условие внутренности

В отличие от методов активных множеств, этот подход требует, чтобы каждый итеративный шаг $x$ оставался строго допустимым ($f_i(x) < 0$). Поскольку логарифм не определён для неотрицательных значений, он создаёт «непреодолимый» барьер, удерживающий поиск внутри внутренней области допустимого множества.

🎯 Определение: методы внутренней точки
Методы внутренней точки: методы решения задач выпуклой оптимизации, включающие неравенства, путём применения метода Ньютона к последовательности задач с равенствами.